import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

/**
 * 反转链表 II
 * 题目：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 * <p>
 * 说明:
 * 1 ≤m≤n≤ 链表长度。
 * <p>
 * 示例:
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 * <p>
 * 来源：力扣（LeetCode-92）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 *
 * @author godfrey
 * @since 2020-12-07
 */
@DisplayName("反转链表 II")
public class ReverseBetween extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments(
                        new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))), 2, 4));
    }

    @DisplayName("迭代法-时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < m - 1; ++i) {
            prev = prev.next;
        }
        ListNode head2 = prev;
        prev = head2.next;
        ListNode cur = prev.next;
        for (int i = m; i < n; ++i) {
            prev.next = cur.next;
            cur.next = head2.next;
            head2.next = cur;  // 头插法
            cur = prev.next;
        }
        System.out.println(dummy.next);
    }
}
